This application claims the priority of Korean Patent Application No. 10-2004-0091577, filed on Nov. 10, 2004, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.
1. Field of the Invention
The present invention relates to a method and apparatus for generating a keystream, and more particularly, to a method and apparatus for generating a keystream, which are suitable for a ubiquitous computing and network environment and provide high security and efficiency.
2. Description of the Related Art
In modern cryptography, there are two kinds of ciphers, i.e., symmetric ciphers and asymmetric ciphers.
Symmetric ciphers are classified into stream ciphers and block ciphers. Stream ciphers are generated by performing a bitwise XOR operation on a sequence of random bits and a plaintext desired to be protected. Stream ciphers are a practical application of one time pads which are considered secure from the viewpoint of information theory.
Block ciphers are designed based on Shannon's theory that more secure and more robust ciphers can be generated by repeatedly performing a substitution operation and a permutation operation, i.e., by repeatedly using a round function, which is considered relatively weak.
A keystream generated by an apparatus for generating a keystream can be used as a key or a pseudo-random number, which is a core element of an information protection service that involves encryption/decryption, authentication, and integrity. An apparatus for generating a keystream is closely related to stream ciphers. Currently, various types of stream ciphers generated using block ciphers or linear feedback shift registers (LFSRs) have been developed.
Specifically, stream ciphers may be generated by applying modes of operation of a block cipher or using some of a plurality of rounds of a block cipher rather than using the entire rounds of a block cipher. Alternatively, stream ciphers may be generated by combining at least one LFSR with a nonlinear Boolean function.
A data communication environment is expected to evolve in the near future into a ubiquitous computing and network environment, such as radio frequency identification (RFID)/ubiquitous sensor network (USN). Such a ubiquitous computing and network environment requires devices to be small, light, cheap, and mobile. In this regard, traditional stream cipher technology may be considered inappropriate for such a ubiquitous environment which is highly resource-constrained.
The self-shrinking generator (SSG) has been suggested by W. Meier and O. Staffelbach (in Eurocrypt '94) as a way to solve the problems with stream cipher-based technology. SSG, which serves as an apparatus for generating a keystream, receives two bits from an LFSR and determines whether a least significant bit of the two bits has a logic value of 1. Thereafter, if the least significant bit has a logic value of 1, SSG outputs a most significant bit of the two bits. If the least significant bit has a logic value of 0, SSG discards the most significant bit.
SSG, however, has limited application to various types of cryptography. In particular, there is a limitation in meeting the various requirements of a ubiquitous environment concerning security and efficiency.